package week_seven;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class RedundantConnectionBFS_684 {
    //出边数组
    private List<List<Integer>> edgeList;
    private int[] inDeg;
    private int[][] edgeLeft;

    public int[] findRedundantConnection(int[][] edges) {
        edgeList = new ArrayList<>();
        //n个顶点
        int n = 0;
        for(int[] edge : edges){
            n = Math.max(n, edge[1]);
        }

        inDeg = new int[n+1];
        edgeLeft = new int[n+1][n+1];

        for (int i = 0; i <= n; i++) {
            edgeList.add(new ArrayList<Integer>());
        }

        for(int[] edge : edges){
            int i = edge[0];
            int j = edge[1];
            addEdge(i, j);
            addEdge(j, i);
            inDeg[i]++;
            inDeg[j]++;
            edgeLeft[i][j]=1;
            edgeLeft[j][i]=1;
        }

        Queue<Integer> queue = new LinkedList<>();

        for(int i = 1;i<=n;i++){
            if(inDeg[i]==1)queue.offer(i);
        }
        while(!queue.isEmpty()){
            int curr = queue.poll();
            for(int y : edgeList.get(curr)){
                inDeg[curr]--;
                inDeg[y]--;
                edgeLeft[y][curr]=0;
                edgeLeft[curr][y]=0;
                if(inDeg[y]==1) queue.offer(y);
            }
        }

        for(int i=edges.length-1;i>=0;i--){
            int a = edges[i][0];
            int b = edges[i][1];
            if(edgeLeft[a][b]==1) return new int[]{a,b};
        }

        return null;

    }

    private void addEdge(int x, int y){
        edgeList.get(x).add(y);
    }
}
